
#include "HNGround.h"
#import "HNQueue.h"
#import "HeroNuts.h"

/*
int MapData[MAP_HEIGHT * MAP_WIDTH] = 
{
#ifdef MAP_1
	1,1,1,1,0,0,0,0,0,1,1,1,1,1,1,
	1,1,1,1,0,0,0,0,1,1,1,1,1,1,1,
	1,1,1,1,0,0,1,1,1,1,1,1,1,1,1,
	1,1,1,0,0,1,1,1,1,1,0,1,1,1,1,
	1,1,0,0,0,1,1,1,0,0,0,1,1,1,1,
	1,1,1,1,1,1,1,0,0,0,1,1,1,1,0,
	0,1,1,1,1,1,1,0,0,1,1,1,1,0,0,
	0,1,1,1,1,1,0,0,1,1,1,1,0,0,0,
	0,0,1,1,1,0,0,1,1,1,0,1,0,0,0,
	0,0,0,1,0,0,0,1,1,1,0,1,1,1,1,
	0,0,0,0,0,1,1,1,1,1,0,1,1,1,0,
  
  
#else
#ifdef MAP_2
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
  
#else
#ifdef MAP_3
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
  
  
#endif // MAP_3
#endif // MAP_2
#endif // MAP_1
};
*/

static int GetStep(int Position, int *pStepNo, const int * outputMap);
int GetY(int x)
{
	return x/MAP_WIDTH;
}
int GetX(int x)
{
	return x%MAP_WIDTH;
}


int CreatePoint(int x,int y)
{
	return y*MAP_WIDTH + x;
}


int GetNearPoint(int pos,int type)
{
	switch (type)
	{
    case LEFT_TOP:
      if (GetY (pos) == 0 || (GetY (pos) % 2 ==1 && GetX (pos)==0))
      {
        return -1;
      }
      return pos - MAP_WIDTH - GetY (pos)%2;
      break;
    case RIGHT_TOP:
      if (GetY (pos) == 0 || (GetY (pos)%2==0 && GetX (pos) == MAP_WIDTH - 1))
      {
        return -1;
      }
      return pos - MAP_WIDTH + 1- GetY (pos)%2;
      break;
    case RIGHT:
      if (GetX (pos) == MAP_WIDTH - 1)
      {
        return -1;
      }
      return pos + 1;
      break;
    case RIGHT_BOTTOM:
      if (GetY (pos) == MAP_HEIGHT - 1 || (GetY (pos)%2==0&&GetX (pos)== MAP_WIDTH - 1))
      {
        return -1;
      }
      return pos + MAP_WIDTH + 1 - GetY (pos)%2;
      break;
    case LEFT_BOTTOM:
      if (GetY (pos) == MAP_HEIGHT - 1 ||(GetY (pos) % 2 ==1 && GetX (pos)==0))
      {
        return -1;
      }
      return pos + MAP_WIDTH - GetY (pos)%2;
      break;
    case LEFT:
      if (GetX (pos) == 0)
      {
        return -1;
      }
      return pos - 1;
      break;
	}
	return -1;
}


void GetCanWalk(int * MapData,int  Pos_Start,int * outputMap,int Max_step, int *arrayCanWalk)
{
	HNQueue *Que = [[[HNQueue alloc] init] autorelease];
	int StepNo = 1,Position,CurrentPos;
  int numberOfArray = 0;
	outputMap[Pos_Start] = StepNo;
	[Que push:Pos_Start];
	for (;;)
	{
		if ([Que empty])
		{
			return;
		}
		CurrentPos = [Que front];
		[Que pop];
		StepNo = outputMap[CurrentPos];
		if (StepNo > Max_step)
		{
			continue;
		}
		for (int i = 0;i < DIRECTION_COUNT;i++)
		{
			Position = GetNearPoint (CurrentPos,i);
			if (Position>=0&&MapData[Position] != 0)
			{
				if (outputMap[Position] == 0 ||
            outputMap[Position] > StepNo +1)
				{
					outputMap[Position] = StepNo+1;
          arrayCanWalk[Position] = 1;
          NSLog(@"area contains X:%d Y:%d",GetX(Position),GetY(Position) );
          numberOfArray ++;
					[Que push:Position];
				}
			}
		}
	}
}

void GetCanWalk2(int * MapData,int Pos_Start,int * outputMap,int Max_step, int *arrayCanWalk)
{
  
	HNQueue *Que = [[[HNQueue alloc] init] autorelease];
	int StepNo = 1,Position,CurrentPos;
  int numberOfArray = 0;
	outputMap[Pos_Start] = StepNo;
	[Que push:Pos_Start];
	for (;;)
	{
		if ([Que empty])
		{
			return;
		}
		CurrentPos = [Que front];
		[Que pop];
		StepNo = outputMap[CurrentPos];
		if (StepNo > Max_step)
		{
			continue;
		}
		for (int i = 0;i < DIRECTION_COUNT;i++)
		{
			Position = GetNearPoint (CurrentPos,i);
			if (Position>=0&&MapData[Position] != 0)
			{
				if (outputMap[Position] == 0 ||
            outputMap[Position] > StepNo +1)
				{
          int bRighPosHasSomething = 
          GetNearPoint (Position,RIGHT);//check the right pos
					if (bRighPosHasSomething >=0 &&
              MapData[bRighPosHasSomething]!=0)
					{
            outputMap[Position] = StepNo+1;
            arrayCanWalk[Position]=1;
            arrayCanWalk[bRighPosHasSomething]=1;
            NSLog(@"area contains X:%d Y:%d",GetX(Position),GetY(Position) );
            numberOfArray ++;
            [Que push:Position];
          }
				}
			}
		}
	}
}

void GetCanFly(int * MapData,int Pos_Start,int * outputMap,int Max_step, int *arrayCanWalk)
{
	int MapDataTemp[MAP_SIZE];
	memcpy(MapDataTemp,MapData,MAP_SIZE*sizeof(4));
	for (int i = 0;i < MAP_SIZE;i++)
	{
		MapData[i] = 1;
	}
  
	GetCanWalk (MapData,Pos_Start,outputMap,Max_step,arrayCanWalk);
  
	for (int i = 0;i < MAP_SIZE;i++)
	{
		if (MapDataTemp[i]== 0 )
		{
			outputMap[i] = 0;
      arrayCanWalk[i]=0;
		}
	}
	memcpy(MapData,MapDataTemp,MAP_SIZE*sizeof(int));
}

void GetCanFly2(int * MapData,int Pos_Start,int * outputMap,int Max_step, int *arrayCanWalk)
{
	int MapDataTemp[MAP_SIZE];
	memcpy(MapDataTemp,MapData,MAP_SIZE*sizeof(4));
	for (int i = 0;i < MAP_SIZE;i++)
	{
		MapData[i] = 1;
	}
  
	GetCanWalk (MapData,Pos_Start,outputMap,Max_step,arrayCanWalk);
  
	for (int i = 0;i < MAP_SIZE;i++)
	{
		if (MapDataTemp[i]== 0 )
		{
			outputMap[i] = 0;
      arrayCanWalk[i]=0;
			continue;
		}
		int pt = GetNearPoint (i,RIGHT);
		if (pt < 0)
		{
			outputMap[i] = 0;
      arrayCanWalk[i]=0;
			continue;
		}
		if (MapDataTemp[pt] == 0)
		{
			outputMap[i] = 0;
      arrayCanWalk[i]=0;
			continue;
		}
	}
	memcpy(MapData,MapDataTemp,MAP_SIZE*sizeof(int));
}



int GetWalkRoute(int * MapData,int StartPos, int TargetPos,const int * outputMap,NSMutableArray * PrintMap)
{
	if (outputMap[StartPos]*outputMap[TargetPos] == 0)
	{
		return -1;
	}
	int Path[MAP_SIZE] = {0};
	int Step = outputMap[TargetPos];
	int index = 0;
	int Pos = TargetPos;
	Path[index++] = Pos;
	do 
	{
		Pos = GetStep(Pos, &Step,outputMap);
		if (Pos != -1)
		{
			Path[index++] = Pos;
			if (Pos == StartPos)
			{
				break;
			}
		}
		else
			break;
    
	} while(true);
  
	int ret = index;
  
	int iPos;
	for (int loop = index-1; loop > -1; loop--)
	{
		iPos = Path[loop];
		//PrintMap[iPos] = 1;
    [PrintMap addObject:[NSNumber numberWithInt:iPos]];
	}
	return ret;
}

int GetFlyRoute(int * MapData,int StartPos, int TargetPos,int * Path)
{
	int cx = GetY (StartPos) - GetY (TargetPos);
	cx = cx>0?cx:-cx;
	int cy = GetX (StartPos) - GetX (TargetPos);
	cy = cy>0?cy:-cy;
	int max_step = cx + cy +2;
	int MapDataTemp[MAP_SIZE];
	memcpy(MapDataTemp,MapData,MAP_SIZE*sizeof(4));
	for (int i = 0;i < MAP_SIZE;i++)
	{
		MapData[i] = 1;
	}
	int outputMap[MAP_SIZE]={0};
	GetCanWalk (MapData,StartPos,outputMap,max_step,nil);
	//int ret  = GetWalkRoute (MapData,StartPos,TargetPos,outputMap,Path);
  
	memcpy(MapData,MapDataTemp,MAP_SIZE*sizeof(int));
	return 0;//ret
}

int GetStep(int Position, int *pStepNo,const int * outputMap)
{
	for (int i = 0;i < DIRECTION_COUNT;i++)
	{
		int pos = GetNearPoint (Position,i);
		if (pos>=0&&outputMap[pos] != 0 && outputMap[pos] < *pStepNo)
		{
			*pStepNo = outputMap[pos];
			return pos;
		}
	}
	return -1;
}

void PrintOutMap(int * pdata)
{
	printf ("    ");
	for (int i = 0;i < MAP_WIDTH;i++)
	{
		printf ("%2d ",i);
	}
	printf ("\n");
	for (int i = 0;i < MAP_HEIGHT;i++)
	{
		printf ("%2d ",i);
		if (i%2==0)
		{
			printf (" ");
		}
		for (int j = 0;j < MAP_WIDTH;j++)
		{
			int dis = pdata[i*MAP_WIDTH + j];
			if (dis == 0)
			{
				printf (" **");
			}
			else
			{
				printf(" %02d", dis);
			}
		} 
		printf ("\n");
	}
	printf ("------------------------------------------\n");
}

